package com.duoduo.递归回溯;

import com.duoduo.栈和队列.接雨水42;

import java.util.ArrayList;
import java.util.List;

/**
 * @program: algorithm
 * @description: 全排列46
 * 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
 * 输入：nums = [1,2,3]
 * 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
 *78
 * 示例 2：
 *
 * 输入：nums = [0,1]
 * 输出：[[0,1],[1,0]]
 * @author: chaidl  ！
 * @create: 2022-03-24 15:45
 */
public class 全排列46 {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result=new ArrayList<>();
        backtrack(result,new ArrayList<Integer>(),nums);
        return result;
    }

    private void backtrack(List<List<Integer>> list, List<Integer> tempList, int[] nums) {
        //终止条件，如果数字都被使用完了，说明找到了一个排列，（可以把它看做是n叉树到
        //叶子节点了，不能往下走了，所以要返回）
        if (tempList.size() == nums.length) {
            //因为list是引用传递，这里必须要重新new一个
            list.add(new ArrayList<>(tempList));
            return;
        }
        //（可以把它看做是遍历n叉树每个节点的子节点）
        for (int i = 0; i < nums.length; i++) {
            //因为不能有重复的，所以有重复的就跳过
            if (tempList.contains(nums[i])) {
                continue;
            }
            //选择当前值
            tempList.add(nums[i]);
            //递归（可以把它看做遍历子节点的子节点）
            backtrack(list, tempList, nums);
            tempList.remove(tempList.size() - 1);
        }

    }
    public static void main(String[] args) {
        全排列46 oo=new 全排列46();
        List<List<Integer>> permute = oo.permute(new int[]{1, 2, 3});
        System.out.println(permute);
    }
}
